// https://www.lintcode.com/problem/next-greater-element-ii/my-submissions

class Solution {
public:
    /**
     * @param nums: an array
     * @return: the Next Greater Number for every element
     */
    vector<int> nextGreaterElements(vector<int> &nums) {
        //法一：双循环向后找大的
        // int len = nums.size();
        // vector<int> record(len, -1);
        // for (int i = 0; i < len; ++i)
        // {
        //     for (int j = i + 1; j < len * 2; ++j)
        //     {
        //         if (nums[j % len] > nums[i])
        //         {
        //             record[i] = nums[j % len];
        //             break;
        //         }
        //     }
        // }
        
        
        // 法二：单调栈，个
        // stack<int> s;
        // vector<int> newNums = nums;
        // newNums.insert(newNums.end(), nums.begin(), nums.end());
        // vector<int> res;
        // int n = nums.size();
        // for (int i = n * 2 - 1; i >= 0; --i) {
        //     while (!s.empty() && s.top() <= newNums[i]) {
        //         s.pop();
        //     }
        //     if (i < n) {
        //         if (s.empty()) {
        //             res.push_back(-1);
        //         } else {
        //             res.push_back(s.top());
        //         }
        //     }
        //     s.push(newNums[i]);
        // }
        // reverse(res.begin(), res.end());
        // return res;

        
        //法二：单调栈；存idx比较好；反过来想，能被当前数弹出来的数的结果是当前数。
        stack<int> idx;
        int len = nums.size();
        vector<int> result(len, -1);
        for (int i = 0; i < len * 2; ++i)
        {
            int num = nums[i % len];
            while (!idx.empty() && nums[idx.top()] < num)
            {
                result[idx.top()] = num;
                idx.pop();
            }
            if (i < len) idx.push(i); //栈里面存的都是要更新到result的
        }
        return result;
    }
};